import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.concurrent.ThreadLocalRandom;


import static org.junit.Assert.*;

public class RedBTree {

}

class RedBlackTree{
    enum Color{
        RED,BLACK
    }
    static class Node{
        int key;
        Object value;
        Node left;
        Node right;
        Node parent; //父节点
        Color color = Color.RED; //颜色

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public Node(int key) {
            this.key = key;
        }

        public Node(int key, Color color) {
            this.key = key;
            this.color = color;
        }
        //是否是左孩子
        private boolean isleftChild(){
            return parent != null && parent.left == this;
        }
        //叔叔节点
        Node uncle(){
            if (parent == null || parent.parent == null){
                return null;
            }
            if (parent.isleftChild()){
                return parent.parent.left;
            }else {
                return parent.parent.right;
            }
        }
        //兄弟节点
        Node sibling(){
            if (parent == null){
                return null;
            }
            if (parent.isleftChild()){
                return parent.right;
            }else {
                return parent.left;
            }
        }
    }
    Node root;

    //判断红
    public boolean isRed(Node node){
        return node != null && node.color == Color.RED;
    }
    //判断黑
    public boolean isBlack(Node node){
        return node == null || node.color == Color.BLACK;
    }
    //右旋
    public void rightRotate(Node pink){
        Node parent = pink.parent;
        Node yellow = pink.left;
        Node green = yellow.right;
        if (green != null){
            green.parent = pink;
        }
        yellow.right = pink;
        yellow.parent = parent;
        pink.left = green;
        pink.parent = yellow;
        if (parent == null){
            root = yellow;
        }else if (parent.left == pink){
            parent.left = yellow;
        }else {
            parent.right = yellow;
        }
    }
    //左旋
    public void leftRotate(Node pink){
        Node parent = pink.parent;
        Node yellow = pink.right;
        Node green = yellow.left;
        if (green != null){
            green.parent = pink;
        }
        yellow.left = pink;
        yellow.parent = parent;
        pink.right = green;
        pink.parent = yellow;
        if (parent == null){
            root = yellow;
        }else if (parent.left == pink){
            parent.left = yellow;
        }else {
            parent.right = yellow;
        }
    }
    /**
     * 新增或更新
     * <br>
     * 正常增、遇到红红不平衡进行调整
     *
     * @param key   键
     * @param value 值
     */
    public void put(int key, Object value){
        Node p = root;
        Node parent = null;
        while (p != null){
            parent = p;
            if (key < p.key){
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                p.key = key;
                return;
            }
        }
        Node inserted = new Node(key,value);
        if (parent == null){
            root = inserted;
        } else if (parent.key < key) {
            parent.right = inserted;
            inserted.parent = parent;
        }else {
            parent.left = inserted;
            inserted.parent = parent;
        }
        //对树颜色进行调整
    }
    private void fixRedRed(Node x){
        // case 1 插入节点是根节点，变黑即可
        if (x == root){
            x.color = Color.BLACK;
            return;
        }
        // case 2 插入节点父亲是黑色，无需调整
        if (isBlack(x.parent)){
            return;
        }
        /* case 3 当红红相邻，叔叔为红时
            需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
        */
        Node parent = x.parent;
        Node uncle = x.uncle();
        Node grandparent = parent.parent;
        if (isRed(uncle)){
            parent.color = Color.BLACK;
            uncle.color = Color.BLACK;
            grandparent.color = Color.RED;
            fixRedRed(grandparent);
            return;
        }
        // case 4 当红红相邻，叔叔为黑时
        if (parent.isleftChild() && x.isleftChild()){ // LL
            parent.color = Color.BLACK;
            grandparent.color = Color.RED;
            rightRotate(grandparent);
        }else if (parent.isleftChild() && !x.isleftChild()){ //LR
            leftRotate(parent);
            x.color = Color.BLACK;
            grandparent.color = Color.RED;
            rightRotate(grandparent);
        } else if (!parent.isleftChild() && !x.isleftChild()) {//RR
            parent.color = Color.BLACK;
            grandparent.color = Color.RED;
            leftRotate(grandparent);
        }else {//RL
            rightRotate(parent);
            x.color = Color.BLACK;
            grandparent.color = Color.RED;
            leftRotate(grandparent);
        }
    }
    /**
     * 删除
     * <br>
     * 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
     *
     * @param key 键
     */
    public void remove(int key){
        Node delete = find(key);
        if (delete == null){
            return;
        }
        doRemove(delete);
    }

    private void doRemove(Node delete){
        Node replace = findReplace(delete);
        Node parent = delete.parent;
        // @TODO 没有孩子
        if (replace == null){
            // case 1 删除的是根节点
            if (delete == root){
                root = null;
            }else {
                if (isBlack(delete)){
                    //双黑调整
                    fixDoubleBlack(delete);
                }else {
                    //红色叶子，不需要调整
                }
            }
            if (delete.isleftChild()){
                parent.left = null;
            }else {
                parent.right = null;
            }
            delete.parent = null;
        }
        //@TODO 有一个孩子
        if (replace.left == null || replace.right == null){
            // case 1 删除的是根节点
            if (delete == root){
                root.key = delete.key;
                root.value = delete.value;
                root.left = root.right = null;
            }else {
                if (delete.isleftChild()){
                    parent.left = replace;
                }else {
                    parent.right = replace;
                }
                replace.parent = parent;
                delete.left = delete.right = delete.parent = null;
                if (isBlack(delete) && isBlack(replace)){
                    // @TODO 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑
                    fixDoubleBlack(replace);
                }else {
                    // case 2 删除是黑，剩下是红
                    replace.color = Color.BLACK;
                }
            }
        }
        // @TODO 有两个孩子=>转变为一个孩子
        int t = delete.key;
        delete.key = replace.key;
        replace.key = t;

        Object value = delete.value;
        delete.value = replace.value;
        replace.value = value;
        doRemove(replace);
    }
    // 处理双黑 (case3、case4、case5)
    private void fixDoubleBlack(Node node){
        if (node == root){
            return;
        }
        Node parent = node.parent;
        Node sibling = node.sibling();
        // case 3 兄弟节点是红色
        if (isRed(sibling)){
            if (node.isleftChild()){
                leftRotate(parent);
            }else {
                rightRotate(parent);
            }
            parent.color = Color.RED;
            sibling.color = Color.BLACK;
            fixDoubleBlack(node);
            return;
        }
        if (sibling != null){
            // case 4 兄弟是黑色, 两个侄子也是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)){
                sibling.color = Color.RED;
                if (isRed(parent)){
                    parent.color = Color.BLACK;
                }else {
                    fixDoubleBlack(parent);
                }
            }else {// case 5 兄弟是黑色, 侄子有红色
                //LL
                if (sibling.isleftChild() && isRed(sibling.left)){
                    rightRotate(parent);
                    sibling.left.color = Color.BLACK;
                    sibling.color = parent.color;
                }else if (sibling.isleftChild() && isRed(sibling.right)){//LR
                    sibling.right.color = parent.color;
                    leftRotate(sibling);
                    rightRotate(parent);
                }else if (!sibling.isleftChild() && isRed(sibling.right)){//RR
                    leftRotate(parent);
                    sibling.right.color = Color.BLACK;
                }else {  //RL
                    sibling.left.color = parent.color;
                    rightRotate(sibling);
                    leftRotate(parent);
                }
                parent.color = Color.BLACK;
            }
        }else {
            // @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null
            fixDoubleBlack(parent);
        }
    }
    // 查找删除节点
    private Node find(int key){
        Node p = root;
        while (p != null){
            if (p.key < key){
                p = p.right;
            }else if (key < p.key){
                p = p.left;
            }else {
                return p;
            }
        }
        return null;
    }
    // 查找剩余节点
    private Node findReplace(Node delete){
        if (delete.left == null && delete.right == null){
            return null;
        }
        if (delete.left == null){
            return delete.right;
        }
        if (delete.right == null){
            return delete.left;
        }
        Node s = root.right;
        while (s.left != null){
            s = s.left;
        }
        return s;
    }
}
